package leetcode.weekly.week321;

import java.awt.Point;
import java.util.HashMap;
import java.util.Map;

//Solution4Test
public class Solution4 {

	public int countSubarrays(int[] nums, int k) {
		int p = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == k) {
				p = i;
				break;
			}
		}
		int ans = 0;
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = p, g = 0, l = 0; i >= 0; i--) {
			int num = nums[i];
			if (num > k) {
				g++;
			} else if (num < k) {
				l++;
			}
			map.put(g - l, map.getOrDefault(g - l, 0) + 1);
		}
		for (int i = p, g = 0, l = 0; i < nums.length; i++) {
			int num = nums[i];
			if (num > k) {
				g++;
			} else if (num < k) {
				l++;
			}
			ans += map.getOrDefault(l - g, 0);
			ans += map.getOrDefault(l - g + 1, 0);
		}
		return ans;
	}
}
